uva 439

ACM
评论

《算法入门》P177
和poj 2243一毛一样。然而。。。这个的时限是3000ms那个是1000ms，而且，当年Floyd的代码0ms过。这意味着什么？这意味着数据太弱，暴力乱过呀！我当年TLE的代码们终于以13ms的成绩从见天日了。

方法一，赤裸裸的广搜： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include<vector>
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<numeric>
#include<algorithm>
using namespace std;
#pragma comment(linker, "/STACK:10240000000,10240000000")
#define inf 0x3ffffff
#include<vector>
#include<queue>
#define mx 1000004
#define mem(x,y) memset(x,y,sizeof(x))
#define mec(x,y) memcpy(x,y,sizeof(x))
#define eps 1e-5
#define mod 1000000007
#define mp(x,y) make_pair(x,y)
int vis[10][10];
int step[10][10];
bool cango(int x,int y)
{
    return x>=1&&x<=8&&y>=1&&y<=8;
}
int X[]={-1,-2,1,2,1,2,-1,-2},Y[]={-2,-1,-2,-1,2,1,2,1};
int main()
{
    char s1[5],s2[5];
    while(~scanf("%s%s",s1,s2))
    {
        printf("To get from %s to %s takes ",s1,s2);
        int x1=s1[0]-'a'+1,x2=s2[0]-'a'+1;
        int y1=s1[1]-'0',y2=s2[1]-'0';
        queue<pair<int,int> >q;
        q.push(mp(x1,y1));
        mem(vis,0);
        mem(step,0);
        while(!q.empty())
        {
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            vis[x][y]=1;
            if(x==x2&&y==y2)
            {
                printf("%d knight moves.\n",step[x][y]);
                break;
            }
            for(int i=0;i<8;i++)
                if(cango(x+X[i],y+Y[i])&&!vis[x+X[i]][y+Y[i]])
                {
                    q.push(mp(x+X[i],y+Y[i]));
                    step[x+X[i]][y+Y[i]]=step[x][y]+1;
                }
        }
    }
}

方法二，避免重复的广搜：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<string.h>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define mem(x,y) memset(x,y,sizeof(x))
#define maxn 50008
#define maxe 400008
#define inf 0x3f3f3f3f
#define mp(x,y) make_pair(x,y)
using namespace std;
int vis[10][10];
int step[10][10];
bool cango(int x,int y)
{
    return x>=1&&x<=8&&y>=1&&y<=8;
}
int X[]={-1,-2,1,2,1,2,-1,-2},Y[]={-2,-1,-2,-1,2,1,2,1};
int a[10][10][10][10];
int main()
{
    for(int x1=1;x1<9;x1++)
        for(int x2=1;x2<9;x2++)
        for(int y1=1;y1<9;y1++)
        for(int y2=1;y2<9;y2++)
    {
        queue<pair<int,int> >q;
        q.push(mp(x1,y1));
        mem(vis,0);
        mem(step,0);
        while(!q.empty())
        {
            int x=q.front().first;
            int y=q.front().second;
            q.pop();
            vis[x][y]=1;
            if(x==x2&&y==y2)
            {
                a[x1][y1][x2][y2]=step[x][y];
                break;
            }
            for(int i=0;i<8;i++)
                if(cango(x+X[i],y+Y[i])&&!vis[x+X[i]][y+Y[i]])
                {
                    q.push(mp(x+X[i],y+Y[i]));
                    step[x+X[i]][y+Y[i]]=step[x][y]+1;
                }
        }
    }
     char s1[5],s2[5];
    while(~scanf("%s%s",s1,s2))
    {
        printf("To get from %s to %s takes ",s1,s2);
        int x1=s1[0]-'a'+1,x2=s2[0]-'a'+1;
        int y1=s1[1]-'0',y2=s2[1]-'0';
        printf("%d knight moves.\n",a[x1][y1][x2][y2]);
    }
}

EOF